๐Ÿ‘ฉโ€๐Ÿ’ป 3190. ๋ฑ€

@Seongukbaek Posted March 18, 2022 ยท Updated March 18, 2022 ยท 6 min read

๋ฌธ์ œ

'Dummy' ๋ผ๋Š” ๋„์Šค๊ฒŒ์ž„์ด ์žˆ๋‹ค. ์ด ๊ฒŒ์ž„์—๋Š” ๋ฑ€์ด ๋‚˜์™€์„œ ๊ธฐ์–ด๋‹ค๋‹ˆ๋Š”๋ฐ, ์‚ฌ๊ณผ๋ฅผ ๋จน์œผ๋ฉด ๋ฑ€ ๊ธธ์ด๊ฐ€ ๋Š˜์–ด๋‚œ๋‹ค. ๋ฑ€์ด ์ด๋ฆฌ์ €๋ฆฌ ๊ธฐ์–ด๋‹ค๋‹ˆ๋‹ค๊ฐ€ ๋ฒฝ ๋˜๋Š” ์ž๊ธฐ์ž์‹ ์˜ ๋ชธ๊ณผ ๋ถ€๋”ชํžˆ๋ฉด ๊ฒŒ์ž„์ด ๋๋‚œ๋‹ค.

๊ฒŒ์ž„์€ NxN ์ •์‚ฌ๊ฐ ๋ณด๋“œ์œ„์—์„œ ์ง„ํ–‰๋˜๊ณ , ๋ช‡๋ช‡ ์นธ์—๋Š” ์‚ฌ๊ณผ๊ฐ€ ๋†“์—ฌ์ ธ ์žˆ๋‹ค. ๋ณด๋“œ์˜ ์ƒํ•˜์ขŒ์šฐ ๋์— ๋ฒฝ์ด ์žˆ๋‹ค. ๊ฒŒ์ž„์ด ์‹œ์ž‘ํ• ๋•Œ ๋ฑ€์€ ๋งจ์œ„ ๋งจ์ขŒ์ธก์— ์œ„์น˜ํ•˜๊ณ  ๋ฑ€์˜ ๊ธธ์ด๋Š” 1 ์ด๋‹ค. ๋ฑ€์€ ์ฒ˜์Œ์— ์˜ค๋ฅธ์ชฝ์„ ํ–ฅํ•œ๋‹ค.

๋ฑ€์€ ๋งค ์ดˆ๋งˆ๋‹ค ์ด๋™์„ ํ•˜๋Š”๋ฐ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทœ์น™์„ ๋”ฐ๋ฅธ๋‹ค.

  • ๋จผ์ € ๋ฑ€์€ ๋ชธ๊ธธ์ด๋ฅผ ๋Š˜๋ ค ๋จธ๋ฆฌ๋ฅผ ๋‹ค์Œ์นธ์— ์œ„์น˜์‹œํ‚จ๋‹ค.
  • ๋งŒ์•ฝ ์ด๋™ํ•œ ์นธ์— ์‚ฌ๊ณผ๊ฐ€ ์žˆ๋‹ค๋ฉด, ๊ทธ ์นธ์— ์žˆ๋˜ ์‚ฌ๊ณผ๊ฐ€ ์—†์–ด์ง€๊ณ  ๊ผฌ๋ฆฌ๋Š” ์›€์ง์ด์ง€ ์•Š๋Š”๋‹ค.
  • ๋งŒ์•ฝ ์ด๋™ํ•œ ์นธ์— ์‚ฌ๊ณผ๊ฐ€ ์—†๋‹ค๋ฉด, ๋ชธ๊ธธ์ด๋ฅผ ์ค„์—ฌ์„œ ๊ผฌ๋ฆฌ๊ฐ€ ์œ„์น˜ํ•œ ์นธ์„ ๋น„์›Œ์ค€๋‹ค. ์ฆ‰, ๋ชธ๊ธธ์ด๋Š” ๋ณ€ํ•˜์ง€ ์•Š๋Š”๋‹ค.

์‚ฌ๊ณผ์˜ ์œ„์น˜์™€ ๋ฑ€์˜ ์ด๋™๊ฒฝ๋กœ๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ ์ด ๊ฒŒ์ž„์ด ๋ช‡ ์ดˆ์— ๋๋‚˜๋Š”์ง€ ๊ณ„์‚ฐํ•˜๋ผ.

์ž…, ์ถœ๋ ฅ

์ž…๋ ฅ

  • ์ฒซ์งธ ์ค„์— ๋ณด๋“œ์˜ ํฌ๊ธฐ N์ด ์ฃผ์–ด์ง„๋‹ค. (2 โ‰ค N โ‰ค 100) ๋‹ค์Œ ์ค„์— ์‚ฌ๊ณผ์˜ ๊ฐœ์ˆ˜ K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (0 โ‰ค K โ‰ค 100)
  • ๋‹ค์Œ K๊ฐœ์˜ ์ค„์—๋Š” ์‚ฌ๊ณผ์˜ ์œ„์น˜๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ, ์ฒซ ๋ฒˆ์งธ ์ •์ˆ˜๋Š” ํ–‰, ๋‘ ๋ฒˆ์งธ ์ •์ˆ˜๋Š” ์—ด ์œ„์น˜๋ฅผ ์˜๋ฏธํ•œ๋‹ค. ์‚ฌ๊ณผ์˜ ์œ„์น˜๋Š” ๋ชจ๋‘ ๋‹ค๋ฅด๋ฉฐ, ๋งจ ์œ„ ๋งจ ์ขŒ์ธก (1ํ–‰ 1์—ด) ์—๋Š” ์‚ฌ๊ณผ๊ฐ€ ์—†๋‹ค.
  • ๋‹ค์Œ ์ค„์—๋Š” ๋ฑ€์˜ ๋ฐฉํ–ฅ ๋ณ€ํ™˜ ํšŸ์ˆ˜ L ์ด ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค L โ‰ค 100)
  • ๋‹ค์Œ L๊ฐœ์˜ ์ค„์—๋Š” ๋ฑ€์˜ ๋ฐฉํ–ฅ ๋ณ€ํ™˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ, ์ •์ˆ˜ X์™€ ๋ฌธ์ž C๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ. ๊ฒŒ์ž„ ์‹œ์ž‘ ์‹œ๊ฐ„์œผ๋กœ๋ถ€ํ„ฐ X์ดˆ๊ฐ€ ๋๋‚œ ๋’ค์— ์™ผ์ชฝ(C๊ฐ€ 'L') ๋˜๋Š” ์˜ค๋ฅธ์ชฝ(C๊ฐ€ 'D')๋กœ 90๋„ ๋ฐฉํ–ฅ์„ ํšŒ์ „์‹œํ‚จ๋‹ค๋Š” ๋œป์ด๋‹ค. X๋Š” 10,000 ์ดํ•˜์˜ ์–‘์˜ ์ •์ˆ˜์ด๋ฉฐ, ๋ฐฉํ–ฅ ์ „ํ™˜ ์ •๋ณด๋Š” X๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

  • ์ฒซ์งธ ์ค„์— ๊ฒŒ์ž„์ด ๋ช‡ ์ดˆ์— ๋๋‚˜๋Š”์ง€ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ“ Logic

class Info { int second; char direction; public Info (int second, char direction) { this.second = second; this.direction = direction; } }
  • ๋ฑ€์˜ ๋ฐฉํ–ฅ ์ „ํ™˜ ์ •๋ณด๋ฅผ ์ €์žฅํ•˜๋Š” ํด๋ž˜์Šค
class Dummy { Info[] infos; Queue<Pair> queue = new LinkedList<>(); int[][] map; int[] rangeX = { -1, 0, 1, 0 }; int[] rangeY = { 0, 1, 0, -1 }; int mapSize; int directionChanges; int count = 0; int infoIdx = 0; int snakeDir; ... }
  • Dummy ๊ฒŒ์ž„์— ํ•„์š”ํ•œ ๋กœ์ง์„ ๊ตฌํ˜„ํ•˜๋Š” ํด๋ž˜์Šค
  • map ์—์„œ 1์€ ๋ฑ€์˜ ์œ„์น˜, 2๋Š” ์‚ฌ๊ณผ์˜ ์œ„์น˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค.
private void moveSnake(int x, int y) { ... }
  • Queue ๋ฅผ ์ด์šฉํ•ด์„œ ๋ฑ€์˜ ๊ผฌ๋ฆฌ ์ •๋ณด๋ฅผ ์ €์žฅํ•˜๊ณ , ํ•„์š”์— ๋”ฐ๋ผ ๋จผ์ € ๋“ค์–ด์˜จ ์ขŒํ‘œ๋ฅผ outํ•œ๋‹ค.
  • ๋ฑ€์˜ ๋ฐฉํ–ฅ ์ „ํ™˜์„ ์œ„ํ•ด snakeDir ๋ณ€์ˆ˜๋กœ ๋ฑ€์˜ ํ˜„์žฌ ๋ฐฉํ–ฅ์„ ์ €์žฅํ•œ๋‹ค. (0, 1, 2, 3 - ๋ถ, ๋™, ๋‚จ, ์„œ)
  • ์‹œ๊ฐ„์— ๋”ฐ๋ผ infos ์—์„œ ๋ฐฉํ–ฅ ์ „ํ™˜ ์ •๋ณด๋ฅผ ํ™•์ธํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; class Pair { int x; int y; public Pair(int x, int y) { this.x = x; this.y = y; } } class Info { int second; char direction; public Info (int second, char direction) { this.second = second; this.direction = direction; } } class Dummy { Info[] infos; Queue<Pair> queue = new LinkedList<>(); int[][] map; int[] rangeX = { -1, 0, 1, 0 }; int[] rangeY = { 0, 1, 0, -1 }; int mapSize; int directionChanges; int count = 0; int infoIdx = 0; int snakeDir; public Dummy (int N) { mapSize = N; map = new int[N][N]; } public int game(int directionChanges) { snakeDir = 1; this.directionChanges = directionChanges; moveSnake(0, 0); return count; } private void moveSnake(int x, int y) { queue.add(new Pair(x, y)); map[x][y] = 1; if (infoIdx < directionChanges) accessInfo(); x += rangeX[snakeDir]; y += rangeY[snakeDir]; count++; if (checkBoundary(x, y)) return; if (map[x][y] == 1) return; if (map[x][y] != 2) cutTail(); moveSnake(x, y); } private void accessInfo() { if (infos[infoIdx].second == count) { updateDir(); infoIdx++; } } private void updateDir() { if (infos[infoIdx].direction == 'L') { snakeDir = (snakeDir + 3) % 4; } else { snakeDir = (snakeDir + 1) % 4; } } private void cutTail() { if (!queue.isEmpty()) { Pair out = queue.poll(); map[out.x][out.y] = 0; } } private boolean checkBoundary(int x, int y) { return (x < 0 || x >= mapSize || y < 0 || y >= mapSize); } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Dummy dummy = new Dummy(N); int appleCount = Integer.parseInt(br.readLine()); String[] line; for (int i = 0; i < appleCount; i++) { line = br.readLine().split(" "); dummy.map[Integer.parseInt(line[0])-1][Integer.parseInt(line[1])-1] = 2; } int directionChanges = Integer.parseInt(br.readLine()); dummy.infos = new Info[directionChanges]; for (int i = 0; i < directionChanges; i++) { line = br.readLine().split(" "); dummy.infos[i] = new Info(Integer.parseInt(line[0]), line[1].charAt(0)); } br.close(); System.out.println(dummy.game(directionChanges)); } }

โœ๏ธ Review

  • ์›น ๋ฐฑ์—”๋“œ ๊ธฐ๋Šฅ์„ ๊ตฌํ˜„ํ•˜๋Š” ๊ฒƒ์ฒ˜๋Ÿผ, ์š”๊ตฌ์‚ฌํ•ญ ํ•˜๋‚˜ํ•˜๋‚˜์— ํ•ด๋‹นํ•˜๋Š” ๊ธฐ๋Šฅ ๋ฉ์–ด๋ฆฌ๋ฅผ ๋งŒ๋“ค์–ด๋ณด์ž๋Š” ์ƒ๊ฐ์œผ๋กœ ์ ‘๊ทผํ–ˆ๋‹ค. ์‹œ๋ฎฌ๋ ˆ์ด์…˜์€ ์ฃผ์–ด์ง„ ๋กœ์ง ๊ทธ๋Œ€๋กœ ๊ตฌํ˜„๋งŒ ํ•˜๋ฉด ๋˜๋Š” ๊ฒƒ ๊ฐ™๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

Baekjoon : https://www.acmicpc.net/problem/3190

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€